#include "foremost.h"
#include <fstream>
#include <chrono>
fADJ::fADJ(std::string filename)
{
    std::ifstream infile(filename);
    int n = 0, m = 0, u, v;
    std::string help;
    time_t t, w = 1;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            m++;
            this->vertices.emplace(u);
            this->vertices.emplace(v);
            edges[m] = {m, u, v, t, w};
            this->out[u].emplace(m, u, v, t, w);
            this->in[v].emplace(m, u, v, t, w);
        }
    }
    this->n = vertices.size();
    this->m = edges.size();
}
void fADJ::caculate(int x, time_t ta, time_t to) {
    source = x;
    start = ta;
    end = to;
    f.clear();
    parent_edge.clear();
    parent_node.clear();
    children.clear();
    pq.emplace(start, source, 0, 0);
    while (!pq.empty()) {
        auto [t, u, pu, pe] = pq.top();
        pq.pop();
        if (f.contains(u))  continue;
        f[u] = t;
        if (pe != 0) {
            parent_edge[u] = pe;
            parent_node[u] = pu;
            children[pu].emplace(u);
        }
        Edge faker = {0, 0, 0, t, 0};
        for (auto it = out[u].begin(); it != out[u].end(); it++) {
            auto [nid, nu, nv, nt, nw] = *it;
            if (nt + nw > end)  continue;
            if (f.contains(nv))    continue;
            if (f[nu] > nt) continue;
            pq.emplace(nt + nw, nv, u, nid);
        }
    }
}

void fADJ::re_add_edges(std::vector<Edge> new_edges) {
    for (auto e : new_edges) {
        vertices.emplace(e.u);
        vertices.emplace(e.v);
        edges[e.id] = e;
        out[e.u].emplace(e.id, e.u, e.v, e.t, e.w);
        in[e.v].emplace(e.id, e.u, e.v, e.t, e.w);
    }
    m = edges.size();
    n = vertices.size();
    caculate(source, start, end);
}

void fADJ::re_delete_edges(std::vector<Edge> old_edges) {
    for (auto e : old_edges) {
        edges.erase(e.id);
        out[e.u].erase(e);
        in[e.v].erase(e);
    }
    m = edges.size();
    n = vertices.size();
    caculate(source, start, end);
}

void fADJ::add_edges(std::vector<Edge> new_edges) {
    f[source] = start;
    for (auto e : new_edges) {
        vertices.emplace(e.u);
        vertices.emplace(e.v);
        edges[e.id] = e;
        out[e.u].emplace(e.id, e.u, e.v, e.t, e.w);
        in[e.v].emplace(e.id, e.u, e.v, e.t, e.w);
        if (e.t >= start && e.t + e.w <= end) {
            if (f.contains(e.u) && f[e.u] <= e.t) {
                if (!f.contains(e.v) || f[e.v] > e.t + e.w) {
                    pq.emplace(e.t + e.w, e.v, e.u, e.id);
                }
            }
        }
    }
    while (!pq.empty()) {
        auto [t, u, pu, pe] = pq.top();
        pq.pop();
        if (f.contains(u) && f[u] <= t)  continue;
        f[u] = t;
        if (parent_node.contains(u)) {
            children[parent_node[u]].erase(u);
        }
        parent_edge[u] = pe;
        parent_node[u] = pu;
        children[pu].emplace(u);
        Edge faker = {0, 0, 0, t, 0};
        for (auto it = out[u].lower_bound(faker); it != out[u].end(); it++) {
            auto [nid, nu, nv, nt, nw] = *it;
            if (nt + nw > end)  continue;
            if (f.contains(nv) && f[nv] <= nt + nw)    continue;
            pq.emplace(nt + nw, nv, u, nid);
        }
    }
}

void fADJ::delete_edges(std::vector<Edge> old_edges) {
    f[source] = start;
    red_set.clear();
    for (auto e : old_edges) {
        edges.erase(e.id);
        out[e.u].erase(e);
        in[e.v].erase(e);
        if (parent_edge.contains(e.v) && parent_edge[e.v] == e.id) {
            pq.emplace(f[e.v], e.v, 0, 0);
        }
    }
    while (!pq.empty()) {
        auto [t, u, pu, pe] = pq.top();
        pq.pop();
//        std::cout << u << " " << t << std::endl;
        time_t bestt = 0, beste = 0;
        Edge faker = {0, 0, 0, t, 0};
        for (auto it = in[u].lower_bound(faker); it != in[u].end(); it++) {
            auto& e = *it;
            if (red_set.contains(e.u))  continue;
            if (!f.contains(e.u))   continue;
            if (f[e.u] >= t)    continue;
            if (e.t + e.w > end)  continue;
            if (f[e.u] <= e.t) {
                if (beste == 0 || bestt > e.t + e.w) {
                    bestt = e.t + e.w;
                    beste = e.id;
                }
            }
        }
        if (beste == 0) {
            red_set.emplace(u);
            for (auto child: children[u]) {
                pq.emplace(f[child], child, 0, 0);
            }
        }
        else {
            f[u] = bestt;
            children[parent_node[u]].erase(u);
            parent_edge[u] = beste;
            parent_node[u] = edges[beste].u;
            children[edges[beste].u].emplace(u);
            if (bestt == t) continue;
            red_set.emplace(u);
            for (auto child: children[u]) {
                if (f[child] < bestt) {
                    pq.emplace(f[child], child, 0, 0);
                }
            }
        }
    }
    for (auto node: red_set) {
        children[parent_node[node]].erase(node);
        f.erase(node);
        parent_edge.erase(node);
        parent_node.erase(node);
        children.erase(node);
        time_t bestt = 0, beste = 0;
        for (auto& e: in[node]) {
            if (red_set.contains(e.u))  continue;
            if (!f.contains(e.u))   continue;
            if (f.contains(e.u) && f[e.u] > e.t)  continue;
            if (e.t + e.w > end)    continue;
            if (beste == 0 || bestt > e.t + e.w) {
                bestt = e.t + e.w;
                beste = e.id;
            }
        }
        if (beste != 0) {
            pq.emplace(bestt, node, edges[beste].u, beste);
        }
    }
    while (!pq.empty()) {
        auto [t, u, pu, pe] = pq.top();
        pq.pop();
        if (f.contains(u) && f[u] <= t)  continue;
        f[u] = t;
        if (parent_node.contains(u)) {
            children[parent_node[u]].erase(u);
        }
        parent_edge[u] = pe;
        parent_node[u] = pu;
        children[pu].emplace(u);
        Edge faker = {0, 0, 0, t, 0};
        for (auto it = out[u].lower_bound(faker); it != out[u].end(); it++) {
            auto [nid, nu, nv, nt, nw] = *it;
            if (nt + nw > end)  continue;
            if (f.contains(nv) && f[nv] <= nt + nw)    continue;
            pq.emplace(nt + nw, nv, u, nid);
        }
    }
}


fOSE::fOSE(std::string filename) {
    std::ifstream infile(filename);
    int n = 0, m = 0, u, v;
    std::string help;
    time_t t, w = 1;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            m++;
            this->vertices.emplace(u);
            this->vertices.emplace(v);
            edges.emplace(m, u, v, t, w);
        }
    }
    this->n = vertices.size();
    this->m = edges.size();
}

void fOSE::caculate(int x, time_t ta, time_t to) {
    source = x;
    start = ta;
    end = to;
    f.clear();
    f[source] = start;
    for (auto &e : edges) {
        if (e.t < start)   continue;
        if (e.t + e.w > end) continue;
        if (e.t > end)  break;
        if (!f.contains(e.u))   continue;
        if (f.contains(e.u) && f[e.u] > e.t)   continue;
        if (!f.contains(e.v) || f[e.v] > e.t + e.w) {
            f[e.v] = e.t + e.w;
        }
    }
}

void fOSE::add_edges(std::vector<Edge> new_edges) {
    for (auto e : new_edges) {
        vertices.emplace(e.u);
        vertices.emplace(e.v);
        edges.emplace(e.id, e.u, e.v, e.t, e.w);
    }
    m = edges.size();
    n = vertices.size();
    caculate(source, start, end);
}

void fOSE::delete_edges(std::vector<Edge> old_edges) {
    for (auto e : old_edges) {
        edges.erase(e);
    }
    m = edges.size();
    n = vertices.size();
    caculate(source, start, end);
}

void fstatic_test(std::string filename, int num) {
    std::cout << "static_test" << std::endl;
    fADJ adj(filename);
    fOSE ose(filename);
    for (int i = 1; i <= num; i++) {
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (adj.f.size() != ose.f.size()) {
            std::cout << "size error!!!!" << std::endl;
        }
        for (auto [k, v] : ose.f) {
            if (adj.f.contains(k) && adj.f[k] != v) {
                std::cout << "value error: ";
                std::cout << k << " " << v << " " << adj.f[k] << std::endl;
            }
            if (!adj.f.contains(k)) {
                std::cout << "miss: " << k << " " << v << std::endl;
            }
        }
        std::cout << "finish:" << i << std::endl;
    }
}

template <typename T>
void print_five_num_summary(int index, const std::vector<T>& v) {
    if (v.empty()) {
        return;  // 如果子 vector 为空，不输出
    }

    // 复制并排序原始 vector
    std::vector<T> sorted_v = v;
    std::sort(sorted_v.begin(), sorted_v.end());

    size_t n = sorted_v.size();

    // 计算五个分位数
    auto min = sorted_v.front();
    auto max = sorted_v.back();
    auto median = sorted_v[n / 2];
    auto lower_quartile = sorted_v[n / 4];
    auto upper_quartile = sorted_v[3 * n / 4];

    // 输出索引和五个分位数
    std::cout << index << " "
              << min << " "
              << lower_quartile << " "
              << median << " "
              << upper_quartile << " "
              << max << std::endl;
}

void ffinal_add_test(std::string filename, int vnum, int mnum) {
    std::srand(unsigned(std::time(0)));
    ADJ adj(filename);
    std::vector<int> sf(adj.vertices.begin(), adj.vertices.end());
    std::random_shuffle(sf.begin(), sf.end());
    std::vector<std::vector<int>> hello(3);
    std::vector<std::vector<double>> hello1(2);
    for (int ii = 1; ii <= vnum; ii++) {
        int i = sf[ii];
        std::cout << "start=" << i << ":" << std::endl;
        fADJ adj("");
        fADJ readj("");
        fOSE ose("");
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        readj.caculate(i, 0, std::numeric_limits<time_t>::max());
        std::ofstream outfile;
        outfile.open(std::to_string(i) + "_" + std::to_string(mnum) + "_" "foremostadd.txt", std::ios::out | std::ios::trunc );
        if (infile.is_open()) {
            size_t helpp = adj.f.size();
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % mnum == 0) {
                    auto start = std::chrono::system_clock::now();
                    ose.add_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration1 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[0].push_back(duration1.count());
                    start = std::chrono::system_clock::now();
                    adj.add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration2 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[1].push_back(duration2.count());
                    start = std::chrono::system_clock::now();
                    readj.re_add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration3 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[2].push_back(duration3.count());
                    std::cout << "finish " << m << std::endl;
                    new_edges.clear();
                    hello1[0].push_back((double)(duration1.count()) / (duration2.count()));
                    hello1[1].push_back((double)(duration3.count()) / (duration2.count()));
                    outfile << duration1.count() << " " << duration2.count() << " " << duration3.count() << " " << adj.f.size() << std::endl;
                }
            }
        }
    }
    std::cout << "Integer Vectors Summary:\n";
    for (int i = 0; i < hello.size(); ++i) {
        print_five_num_summary(i, hello[i]);
    }

    std::cout << "\nDouble Vectors Summary:\n";
    for (int i = 0; i < hello1.size(); ++i) {
        print_five_num_summary(i, hello1[i]);
    }
}

void ffinal_delete_test(std::string filename, int vnum, int mnum) {
    std::srand(unsigned(std::time(0)));
    ADJ adj(filename);
    std::vector<int> sf(adj.vertices.begin(), adj.vertices.end());
    std::random_shuffle(sf.begin(), sf.end());
    std::vector<std::vector<int>> hello(3);
    std::vector<std::vector<double>> hello1(2);
    for (int ii = 1; ii <= vnum; ii++) {
        int i = ii;
        std::cout << "start=" << i << ":" << std::endl;
        fADJ adj(filename);
        fADJ readj(filename);
        fOSE ose(filename);
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        readj.caculate(i, 0, std::numeric_limits<time_t>::max());
        std::ofstream outfile;
        outfile.open(std::to_string(i) + "_" + std::to_string(mnum) + "_" "foremostdelete.txt", std::ios::out | std::ios::trunc );
        if (infile.is_open()) {
            size_t helpp = adj.f.size();
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % mnum == 0) {
                    auto start = std::chrono::system_clock::now();
                    ose.delete_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration1 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[0].push_back(duration1.count());
                    start = std::chrono::system_clock::now();
                    adj.delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration2 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[1].push_back(duration2.count());
                    start = std::chrono::system_clock::now();
                    readj.re_delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration3 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[2].push_back(duration3.count());
                    std::cout << "finish " << m << std::endl;
                    new_edges.clear();
                    hello1[0].push_back((double)(duration1.count()) / (duration2.count()));
                    hello1[1].push_back((double)(duration3.count()) / (duration2.count()));
                    outfile << duration1.count() << " " << duration2.count() << " " << duration3.count() << " " << adj.f.size() << std::endl;
                }
            }
        }
        std::cout << "end=" << i << " " << std::endl;
    }
    std::cout << "Integer Vectors Summary:\n";
    for (int i = 0; i < hello.size(); ++i) {
        print_five_num_summary(i, hello[i]);
    }

    std::cout << "\nDouble Vectors Summary:\n";
    for (int i = 0; i < hello1.size(); ++i) {
        print_five_num_summary(i, hello1[i]);
    }
}
